Several techniques have been devised for binary multiplication. One method is the binary equivalent of longhand multiplication. FIG. 1 shows how the multiplication of two unsigned 8-bit operands is performed with the binary equivalent of longhand multiplication. B(0) to B(7) are the digits of the B operand, A(0) to A(7) are the digits of the A operand, and D(0) to D(15) are the digits of the product D of B times A with A(0), B(0) and D(0) being the least significant digits (LS) and A(7), B(7) and D(15) being the most significant digits (MS), respectively.
For each 1 in the multiplier, operand B, a left shifted version of the multiplicand, operand A, is accumulated as a partial product. Thus the final sum of the partial products is the product D.
Often the operands are in "two's complement" format. This means that each one in the operand is converted to a zero, each zero is converted to a one, and finally 1 is added to the result in order to represent negative numbers. For example, the two's complement of 1001 is 0110+1=0111. If the operands are in two complement format, then sign correction must be performed as shown in FIG. 2 to perform a binary longhand multiplication.
In FIG. 2, S is the sign digit with S=0 for a positive operand and S=1 for a negative operand. The partial products that are accumulated are effectively sign extended to 16 bits and S(15) is the sign of the product. If the multiplier B is negative then B(7)=1 and the corresponding partial product should be subtracted rather than added. Rather than provide a special case for this last partial product so that it can be subtracted rather than added, an extra subtraction can be performed as shown in FIG. 2 of the A operand shifted to the MS digit and followed by zeros. This is possible because: EQU -27=+27-28
As can be seen, longhand binary multiplication is conceptually quite simple. Unfortunately, it is costly when implemented due to the large amount of shifting and multiplexing required. One simplification technique has been proposed by A. Booth in "A Signed Binary Multiplication Technique", Quarterly Journal of Mechanics and Applied Mathematics, vol. IV, pt. 2, pp. 236-240 (1951). The Booth technique, shown in FIG. 3 and Table 1 for a two's complement 8.times.8 multiplication, allows the number of partial products to be reduced by a factor of two. Pairs of multiplier (B) bits are encoded into the signed digit set +2, +1, 0, -1, and -2 which multiply the sign extended multiplicand, A. A signed-digit-carry (SDC) is generated between each bit pair since the digit +3 is excluded from the set and passes between pairs of multilier bits. The digit +3 is expressed as the sum of an allowed digit and the SDC-out signal.
TABLE 1 ______________________________________ INPUTS OUTPUTS B (2J+1) B(2J) SDC(2J) MULTIPLIER SDC(2J+2) ______________________________________ 0 0 0 .times.0 0 0 0 1 .times.(+1) 0 0 1 0 .times.(+1) 0 0 1 1 .times.(+2) 0 1 0 0 .times.(-2) 1 1 0 1 .times.(-1) 1 1 1 0 .times.(-1) 1 1 1 1 .times.0 1 ______________________________________
A feature of the Booth set of signed digits as seen in Table 1, is that the SDC-out is independent of the SDC-in. Each resultant signed digit multiplies a left-shifted sign-extended mutliplicand and is accumulated. Sign correction for a negative multiplier, B(7)=1, is the same as described in the longhand multiplication, and an extra addition of this same left shifted A operand is necessary if there is a SDC-out from the last bit pair, SDC(8)=1, as seen in FIG. 3.
A simple example using the Booth encoding set of FIG. 3 and Table 1 is shown in Example 1 for multiplying the binary equivalents of 8.times.3.